package linked;

import java.util.*;
public class Ex138 {
    class Node {
        int val;
        Node next;
        Node random;
    
        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    class Solution {

        //空间复杂度O(n)
        public Node copyRandomList1(Node head) {
           if (head == null) return null;
            Map<Node, Node> map = new HashMap<>();
            Node cur = head, node;
            while (cur != null) {
                map.put(cur, new Node(cur.val));
                cur = cur.next;
            }
            cur = head;
            while (cur != null) {
                node = map.get(cur);
                node.random = map.get(cur.random);
                node.next = map.get(cur.next);
                cur = cur.next;
                node = node.next;
            }
            return map.get(head);
        }

        public Node copyRandomList(Node head) {
            if (head == null) return null;
            Node res = new Node(0), result = res, cur = head, node;
            //变成old=>new=>old=>new结构
            while (cur != null) {
                node = new Node(cur.val);
                node.next = cur.next;
                cur.next = node;
                cur = node.next;
            }
            //构造random指向
            cur = head;
            while (cur != null) {
                cur.next.random = cur.random == null ? null : cur.random.next;
                cur = cur.next.next;
            }
            //拆分两个链表
            res = head.next; //res为链表表指针
            result.next = res;
            cur = head;
            while (cur != null && cur.next != null) {
                 cur.next = res.next;
                 res.next = cur.next == null ? null : cur.next.next;
                 cur = cur.next;
                 res = res.next;
            }
         //    cur.next = null; //最后一个节点有点问题
            return result.next;
         }
    }
    
}
